// 左式堆

template <typename Comparable>
class MyLeftistHeap
{
private:
    struct LeftistNode
    {
        // 节点对象
        Comparable element;
        // 左子节点
        LeftistNode* left;
        // 右子节点
        LeftistNode* right;
        // 零路径长
        int np1;

        /* 左节点构造函数 */
        LeftistNode(const Comparable & e, LeftistNode* lt = nullptr, LeftistNode* rt = nullptr, int np = 0) : element{e}, left{lt}, right{rt}, np1{np} {}
        /* 右值形式的构造函数 */
        LeftistNode(const Comparable && e, LeftistNode* lt = nullptr, LeftistNode* rt = nullptr, int np = 0) : element{e}, left{lt}, right{rt}, np1{np} {}

        // 根节点
        LeftistNode* root;
        /*  */
        LeftistNode* merge(LeftistNode* h1, LeftistNode* h2)
        /*  */
        LeftistNode* merge1(LeftistNode* h1, LeftistNode* h2)

        /* 交换左右子节点 */
        void swapChildren(LeftistNode* t)
        /*  */
        void reClaimMemory(LeftistNode* t)
        /*  */
        LeftistNode* clone(LeftistNode* t) const
    };

    /* 将另一个堆rhs合并到本堆中 */
    void merge(LeftistHeap & rhs)
    {
        // 避免别名问题（要合并的优先队列与本队列同名）
        if(this = &rhs)
            return;
        // 合并两个根
        root = merge(root, rhs.root);
        // 删除原来的根
        rhs.root = nullptr;
    }
    /* 合并两个节点 */
    LeftistNode* merge(LeftistNode* h1, LeftistNode* h2)
    {
        // 当某个节点下是空堆时的操作
        if(h1 == nullptr)
            return h2;
        if(h2 == nullptr)
            return h1;
        // 两个节点均非空堆，则调用合并支持函数
        if(h1->element < h2->element)
            return merge1(h1,h2);
        else
            return merge1(h2,h1);
    }
    /* 
     *  合并支持函数，h1是值较小的节点，h2是值较大的节点。
     *  由左偏性质，h2应当位于h1的下方
    */
    LeftistNode* merge1(LeftistNode* h1, LeftistNode* h2)
    {
        // 若h1左子堆是空堆，将h2则直接合并到左边
        if(h1->left == nullptr)
            h1->left = h2;
        // 
        else
        {
            // 递归，直到某个节点为空堆（叶子层）。这是一个下滤的过程
            h1->right = merge(h1->right, h2);
            // 进行h1子节点零路径长度判断，保证左偏性
            if(h1->left->np1 < h1->right->np1)
                swapChildren(h1);
            // 更新h1零路径长（基于左偏规律）
            h1->np1 = h1->right->np1 + 1;
        }
        // 返回合并后的值
        return h1;
    }

public:
    LeftistHeap()
    LeftistHeap(const LeftistHeap& rhs)
    LeftistHeap(const LeftistHeap&& rhs)

    ~LeftistHeap()

    LeftistHeap& operator=(const LeftistHeap & rhs)
    LeftistHeap& operator=(LeftistHeap && rhs)

    bool isEmpty() const
    const Comparable & findMin() const

    /* 插入x节点，允许项重复 */ 
    void insert(const Comparable & x)
    {
        root = merge(new LeftistNode{x}, root)
    }
    // 右值形式
    void insert(Comparable && x)
    /* 删除最小项 */
    void deleteMin()
    {
        if(isEmpty())
            throw UnderflowException{};

        LeftistNode* oldRoot = root;
        // 看似是合并，但本质是排序（合并的过程包括排序过程）
        root = merge(root->left, root->right);
        delete oldRoot;
    }
    /* 删除最小项并放入minItem */
    void deleteMin(Comparable & minItem)
    {
        minItem = findMin();
        deleteMin();
    }
    /* 删除本堆 */
    void makeEmpty()
    /* 删除指定的堆 */
    void merge(LeftistHeap & rhs)
};
